https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/
//class Solution {
//public:
//
//    int m, n;
//    int cutOffTree(vector<vector<int>>& forest) {
//        m = forest.size(), n = forest[0].size();
//        vector<pair<int, int>> trees;
//
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (forest[i][j] > 1) {
//                    trees.push_back({ i,j });
//                }
//            }
//        }
//
//        sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2) {
//            return forest[p1.first][p1.second] < forest[p2.first][p2.second];
//            });
//
//        int sum = 0;
//        int bx = 0, by = 0;
//        for (auto& [a, b] : trees) {
//            int step = bfs(forest, bx, by, a, b);
//            if (step == -1) {
//                return -1;
//            }
//            sum += step;
//            bx = a, by = b;
//        }
//        return sum;
//    }
//
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//    bool vis[51][51];
//
//    int bfs(vector<vector<int>> forest, int bx, int by, int ex, int ey) {
//
//        if (bx == ex && by == ey) {
//            return 0;
//        }
//
//        memset(vis, 0, sizeof vis);
//        queue<pair<int, int>> qu;
//
//        qu.push({ bx,by });
//        vis[bx][by] = true;
//        int sum = 0;
//
//        while (!qu.empty()) {
//            sum++;
//            int sz = qu.size();
//            while (sz--) {
//                auto [kx, ky] = qu.front();
//                qu.pop();
//                for (int k = 0; k < 4; k++) {
//                    int x = kx + dx[k];
//                    int y = ky + dy[k];
//                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && forest[x][y]) {
//                        if (x == ex && y == ey) {
//                            return sum;
//                        }
//                        qu.push({ x,y });
//                        vis[x][y] = true;
//                    }
//                }
//            }
//
//        }
//        return -1;
//    }
//};


https://leetcode.cn/problems/om3reC/description/

//class Solution {
//public:
//    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
//
//        unordered_set<string> vis;
//        unordered_set<string> hash(wordList.begin(), wordList.end());
//
//        if (beginWord == endWord) {
//            return 0;
//        }
//        if (!hash.count(endWord)) {
//            return 0;
//        }
//
//        int size = endWord.size();
//        queue<string> qu;
//        qu.push(beginWord);
//
//        int sum = 1;
//        while (qu.size()) {
//            sum++;
//            int sz = qu.size();
//            while (sz--) {
//                string s = qu.front();
//                qu.pop();
//                for (int i = 0; i < size; i++) {
//                    string tmp = s;
//                    for (int j = 0; j < 26; j++) {
//                        tmp[i] = (j + 'a');
//                        if (hash.count(tmp) && !vis.count(tmp)) {
//                            if (tmp == endWord) {
//                                return sum;
//                            }
//                            qu.push(tmp);
//                            vis.insert(tmp);
//                        }
//                    }
//                }
//            }
//        }
//
//        return 0;
//    }
//};

https://leetcode.cn/problems/minimum-genetic-mutation/description/
//class Solution {
//public:
//    int minMutation(string startGene, string endGene, vector<string>& bank) {
//
//        unordered_set<string> vis;
//        unordered_set<string> hash(bank.begin(), bank.end());
//        string change = "ACGT";
//
//        queue<string> qu;
//        if (startGene == endGene) {
//            return 0;
//        }
//        if (!hash.count(endGene)) {
//            return -1;
//        }
//
//        qu.push(startGene);
//        vis.insert(startGene);
//
//        int sum = 0;
//        while (qu.size()) {
//            sum++;
//            int sz = qu.size();
//            while (sz--) {
//                string s = qu.front();
//                qu.pop();
//
//                for (int i = 0; i < 8; i++) {
//                    string tmp = s;
//                    for (int j = 0; j < 4; j++) {
//                        tmp[i] = change[j];
//                        if (hash.count(tmp) && !vis.count(tmp)) {
//                            if (tmp == endGene) {
//                                return sum;
//                            }
//                            qu.push(tmp);
//                            vis.insert(tmp);
//                        }
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};

https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
//class Solution {
//public:
//
//    int dx[4] = { -1,1,0,0 };
//    int dy[4] = { 0,0,1,-1 };
//
//    bool vis[301][103];
//    int m, n;
//    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
//        int m = maze.size(), n = maze[0].size();
//        queue<pair<int, int>>qu;
//
//        qu.push({ entrance[0],entrance[1] });
//        vis[entrance[0]][entrance[1]] = true;
//
//        int sum = 0;
//
//        while (qu.size()) {
//            sum++;
//            int sz = qu.size();
//            while (sz--) {
//                auto [a, b] = qu.front();
//                qu.pop();
//
//                for (int k = 0; k < 4; k++) {
//                    int kx = dx[k] + a;
//                    int ky = dy[k] + b;
//                    if (kx >= 0 && kx < m && ky >= 0 && ky < n && !vis[kx][ky] && maze[kx][ky] == '.') {
//                        if (kx == 0 || ky == 0 || kx == m - 1 || ky == n - 1) {
//                            return sum;
//                        }
//                        qu.push({ kx,ky });
//                        vis[kx][ky] = true;
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};